A moving autonomous vehicle typically includes some type of sensor system for gathering information of an environment through which the vehicle navigates. A problem associated with guiding a vehicle is the large amount of computing power required to analyze the scenario in order to identify obstacles and to avoid them in a reliable manner while finding a valid path to a target or destination. The interpretation of data is normally too slow to be useful within a scenario with obstacles in real-time applications.
In general, the term path finding relates to a collection of techniques for finding an optimal (e.g. safest, shortest, etc.) route between two points, namely a source and a target, within a scenario within obstacles. A visibility graph is a roadmap, a route that stores the visibility relationships between a set of objects, considering as obstacles normally defined by polygons. The visibility graph is basically made up of visible nodes and weighted edges. Visible nodes represent safe potential waypoints that are mutually connected by edges. Each edge carries a weight defined by a cost function, which is usually the Euclidean distance between the nodes. The joint of different edges provides a subpath. Thus a subpath defines a way of reaching a waypoint from another waypoint. An optimal path may comprise several subpaths. The creation of a visibility graph is a complex task that usually requires high computational times to provide a feasible response.
Normally visibility-based path finding approaches represent obstacles by geometric figures (e.g. polygons, circles, etc.) since there are no performance losses related to discretization. There are improvements in sophisticated algorithms that make certain simplifications to build a graph, providing, in particular cases, good performance from the computational complexity point of view (e.g. N log N). Yet they consider all the polygons vertices of the scenario as potential waypoints. In addition, they are complex and unintuitive to implement.
In sum, existing approaches build a full graph regardless of the importance of the information of different areas with respect to a source (e.g. the current position) and a target position. As a consequence, they are extremely inefficient in real-time applications and complex environments.
For this reason, known solutions cannot be applied in practice, when obstacles on the travel path are found and quick evasive maneuvers are required. An efficient generation under real-time constraints of a path that is free of obstacles is therefore needed.